# -*- coding: utf-8 -*-

"""
    http://projecteuler.net/problem=21
    
    PROBLEM
    
    Let d(n) be defined as the sum of proper divisors of n (numbers less than
    n which divide evenly into n).

    If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair
    and each of a and b are called amicable numbers.

    For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22,
    44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1,
    2, 4, 71 and 142; so d(284) = 220.

    Evaluate the sum of all the amicable numbers under 10000.

    
    NOTES
    
    
    REFERENCES
    
    
    PERFORMANCE
    time <function test_case at 0x7fe2e1c9c668>: 0.000112 s
    time <function solution at 0x7fe2e1c9c758>: 0.113132 s
    
"""
#
# Import
#
import time


#
# Globals / Constants
#
def timeit(f):
    def timer():
        t0 = time.time()
        returned = f()
        print "time %s: %.6f s" % (f, time.time() - t0)
        return returned
    return timer

def assert_match(value, expected):
    assert value == expected, "value %s != expected %s" % (
        value, expected)


#
# Test Case / Solution
#
@timeit    
def test_case():
    cases = [
        (220, [1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110], 284),
        (284, [1, 2, 4, 71, 142], 220),
    ]
    
    for number, expected_divisors, expected_divisor_sum in cases:
        divisors = get_proper_divisors(number)
        assert_match(divisors, expected_divisors)
        assert_match(sum(divisors), expected_divisor_sum)

    print "test case passed!"

@timeit
def solution():
    return sum_amicable_numbers(10000)
        

#
# Solution Code
#
def sum_amicable_numbers(limit):
    amicable_map = dict()
    amicable_numbers = []
    
    for n in xrange(1,limit):
        divisors = get_proper_divisors(n)
        amicable_map[n] = sum(divisors)
        
    for a in amicable_map:
        b = amicable_map.get(a)
        a_ = amicable_map.get(b)
        
        if b and a == a_ and a != b:
            amicable_numbers += [a,b]
    
    return sum(set(amicable_numbers))
    
def get_proper_divisors(number):
    """proper divisors include all divisors excluding number itself"""
    divisors = [1]
    
    limit = int(round(number**0.5)) + 1
    
    for n in xrange(2, limit):
        if number % n == 0:
            divisors += [n, number/n]
            
    return sorted(divisors)

    

#
# Additional Tests
#



#
# Main
#
if __name__ == '__main__':
    test_case()
    print solution()
    